package com.example.leetcode;

/**
 * 动态规划  贪心算法
 * 跳跃游戏  ** 参考题解 维护最远到达距离 遍历一次
 */
public class Demo0055 {

    //思路1 O(n^2)
    public boolean canJump(int[] nums) {
        int len = nums.length;
        boolean [] fun=new boolean[len];
        fun[0]=true;
        for (int i = 0; i < len; i++) {
            if (fun[i]){
                if (nums[i]+i>=len-1){
                    return true;
                }
                for (int j = i+1; j <=nums[i]+i; j++) {
                    fun[j]=true;
                }
            }else {
                return false;
            }
        }
        return fun[len-1];
    }


    public boolean canJump2(int[] nums) {
        int len = nums.length;
        int right=0;
        for (int i = 0; i < len; i++) {
            //i在左边则需考虑更新right,i跑到右边则不可达
            if (i<=right){
                right=Math.max(right,nums[i]+i);
                if (right>=len-1){
                    return true;
                }
            }else {
                return false;
            }
        }
        return false;
    }

    /**
     * dp
     * 状态方程  f(i)= i及i之前的数据能跨越i多少步(无论从哪跳)
     * 转移方程  f(i+1)=  f(i) 与nums[i]的最大值
     * 边界条件  某个f(i)=0时则跨越不了当前下标 f(0)=num[0]
     */
    public boolean canJump3(int[] nums) {
        if (nums.length==1){
            return true;
        }
        int iSkip=nums[0];
        for (int i = 1; i < nums.length; i++) {
            //过不去i这个坎
            if (iSkip==0){
                return false;
            }
            iSkip=Math.max(iSkip-1,nums[i]);
        }
        //遍历结束则可达
        return true;
    }

    /**
     * 贪心
     * 维护当前能跳多远 maxRight
     * 遍历，当i在最远maxRight右边时说明i已经不可达
     * 当i在最远maxRight左边时尝试更新maxRight
     */
    public boolean canJump4(int[] nums){
        int len = nums.length;
        int maxRight=0;//前面所有最远可达
        for (int i = 0; i < len; i++) {
            if (i<=maxRight){
                maxRight=Math.max(maxRight,i+nums[i]);
                if (maxRight>len-1){
                    return true;
                }
            }else {
                return false;
            }
        }
        //遍历完len-1还没true则到不了
        return false;
    }
}
